package club.babyf.nativeai.demo.algorithm;

/**
 * BinaryTreeInverter.
 *
 * @author zhanglei.
 * @date 2025/5/8 20:57.
 * @description 反转二叉树.
 * 自行构造一个单向二叉树，每个二叉树节点包含且只包含数据节点、左子节点和右子节点，然后替换每个节点的左子节点和右子节点，包括只有单子节点的节点。
 */
public class _12_BinaryTreeInverter {

    public static void main(String[] args) {
        // 手动构造一个示例二叉树
        // 结构如下：
        //       1
        //     /   \
        //    2     3
        //   / \   /
        //  4   5 6
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);

        // 输出原始树的前序遍历结果
        System.out.println("原始树的前序遍历:");
        preOrderTraversal(root);
        System.out.println();

        // 反转二叉树的左右子节点
        // 1）
        invertBinaryTree(root);
        // 2）
//        TreeNode treeNode = invertTree(root);

        // 输出反转后的前序遍历结果
        System.out.println("反转后的前序遍历:");
        preOrderTraversal(root);
        System.out.println();
    }

    public static TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode node = new TreeNode();
        node.val = root.val;
        node.left = invertTree(root.right);
        node.right = invertTree(root.left);
        return node;
    }

    /**
     * 递归反转二叉树的左右子节点
     *
     * @param root 当前处理的二叉树节点
     */
    public static void invertBinaryTree(TreeNode root) {
        if (root == null) {
            return;  // 递归终止条件：空节点直接返回
        }

        // 交换当前节点的左右子节点
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        // 递归处理左右子树（注意：此时left和right已经交换）
        invertBinaryTree(root.left);
        invertBinaryTree(root.right);
    }

    /**
     * 前序遍历二叉树并打印节点值（用于验证结果）
     *
     * @param root 当前遍历的二叉树节点
     */
    public static void preOrderTraversal(TreeNode root) {
        if (root == null) {
            return;  // 递归终止条件：空节点直接返回
        }

        System.out.print(root.val + " "); // 先访问根节点
        preOrderTraversal(root.left);      // 再遍历左子树
        preOrderTraversal(root.right);     // 最后遍历右子树
    }

    static class TreeNode {
        int val;         // 节点数据
        TreeNode left;    // 左子节点
        TreeNode right;   // 右子节点

        public TreeNode() {

        }

        public TreeNode(int val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }

    }

}
